The two-dimensional marker automata is an extension of the 4FA and will be
abbreviated as 2MA($k$) where $k \in \mathbb{N}$ represents the number of
markers. The marker automata was introduced in 1977 by M.Blum and C.Hewitt
in the same paper as the 4FA(see~\cite{blum1967automata}). 

A marker automaton has a set of \emph{labeled markers} $\{m_1, \ldots,
m_k\}$ or set of \emph{unlabeled markers} $\{*, \ldots, *\}$. These markers
can be attached to a pixel of an input picture. The number of markers per
pixel can be limited. A marker is \emph{physical} or \emph{abstract}. To get
the physical marker transferred from one position to another, the automaton must
actually go to the marker and move it to its target. If the automaton places an
abstract marker $m_i$ on a pixel of an input picture, the
marker $m_i$ is removed from its current position and instantly
appears on the target pixel.
Before we will see that the different definitions of markers and marker automata
generate the same class of languages, we want to give a formal definition of a
deterministic 2MA($k$).

The following formal definition is based on the definition of a
two-dimensional alternating $k$-marker automaton by K. Morita
in~\cite{morita2004twodimensional} and represents only one possible definition
of the marker automata.
\begin{definition} 
A \emph{two-dimensional deterministic $k$-marker automaton} $(k \in \mathbb{N})$
abbreviated as 2DMA($k$) is a 7-tuple
$M = (Q, \Sigma, \delta, q_0, \{0, 1\}, F)$, where
\begin{compactitem}
	\item $Q$ is a finite set of states,
	\item $\Sigma$ is a finite input alphabet,
	\item $q_0 \in Q$ the initial state,
	\item $\{0, 1\}$ is the presence and absence sign of markers,
	\item $F \subseteq Q$ is a set of accepting states,
	\item
	$\delta: ((Q \times \{0, 1\}^k) \times ((\Sigma \cup \{\#\}) \times \{0, 1\}^k)) \\
	\rightarrow ((Q \times \{0, 1\}^k) \times ((\Sigma \cup \{\#\}) \times \{0, 1\}^k)) \times \Delta$
	is the control function, where $\# \not\in \Sigma$ is the boundary symbol and
	$\Delta = \{U, D, L, R, N\}$ is the set of directions.
\end{compactitem}
\end{definition}
$Q \times \{0, 1\}^k$ is called the set of all extended states. $(q, u) \in (Q
\times \{0, 1\}^k)$ represents the situation that $M$ is in state $q$ and which
marker, saved in $u$, is currently available. If the value of $u_i$ is equal to
$1$ then $M$ can place the marker $i$. If the value of $u_i$ is equal to $0$,
the automaton $M$ has already placed the marker somewhere else.

$\Sigma \times \{0, 1\}^k$ is called the extended input alphabet.
$(a, v) \in (\Sigma \times \{0, 1\}^k)$ is called an extended input symbol and
represents the situation that $a$ is on the current cell and which marker, saved
in $v$, is placed on this pixel. If the value of $v_i$ is equal to $1$ then $M$
can take the marker $i$ or leave it in its place. Otherwise $M$ can place the marker
$i$ on this pixel if the value of $u_i$ is equal to $1$.

We can see that this definition of a marker automaton defines a marker automaton
with labeled and physical markers where more than one marker can be stacked on a
single pixel. The following three theorems proved by M. Blum and C. Hewitt
in~\cite{blum1967automata} show that the definition of a 2MA($k$) could be
adjusted without losing its quintessence.
\begin{theorem}
A 2MA($k$) that can place at most one marker on a pixel is as powerful as a
2MA($k$) that can stack any number of markers on a pixel.
\end{theorem}
\begin{theorem}
A 2MA($k$) with only abstract markers can be simulated by a 2MA($k$)
with only physical markers and vice versa.
\end{theorem}
\begin{theorem}
For each 2MA($k$) with unlabeled markers it exists a 2MA($k$) with labeled
markers accepting the same language and vice versa.
\end{theorem}
Now we want to show an example how a 2DMA($1$) processes an input picture. At
first, we define the language $L_{1n = cc}$: $L_{1n = cc}$ is the language of
all pictures over $\Sigma = \{0, 1\}$, where the height is at least half as high as the
width of the picture and any picture must have an odd side width. Furthermore,
for any picture in $L_{1n = cc}$ the symbol in the right upper corner and the
symbol in the center of the picture must be the same. Formally $L_{1n = cc}$ can
be defined as
\begin{align*} 
L_{1n = cc} = \{p \mid& p \in \Sigma^{*,*}, 2 \cdot l_1(p) > l_2(p) \text{ and }
l_2(p)\text{ mod } 2 = 1 \\
&\text{ and } p(1, l_2(p))) = p(\lceil l_2(p) / 2 \rceil, \lceil l_2(p) / 2
\rceil)\}.
\end{align*} 
The following picture $p \in L_{1n = cc}$ is one example picture of the language
described above:
\begin{center}
$p = $ \begin{tabular}{|D{0.4cm}|D{0.4cm}|D{0.4cm}|D{0.4cm}|D{0.4cm}|}
\hline
0 & 1 & 1 & 0 & 0 \tabularnewline
\hline
0 & 0 & 1 & 1 & 1 \tabularnewline
\hline
1 & 1 & 0 & 0 & 1 \tabularnewline
\hline
0 & 1 & 1 & 0 & 0 \tabularnewline
\hline
\end{tabular}
\end{center}
We now regard a 2DMA($1$) $M$ that accepts exactly the language $L_{1n = cc}$
that means $L_{1n = cc} = L(M)$.
\begin{example}
$M = (\{q_0, \ldots, q_{11}, q_e\}, \{0, 1\}, \delta, \{0, 1\}, \{q_e\})$ 
\begin{center}
\footnotesize
\begin{tabular}{@{ }c@{ }|@{ }c@{ }|@{ }c@{ }|@{ }c@{ }|@{ }c@{ }|@{ }c@{ }}
$\delta$     & (0,0)                   & (0,1)                 &  (1,0)                   & (1,1)                 &  (\#,0)                 \tabularnewline
\hline
($q_0$,0)    & (($q_1$,0),(0,0),$R$)    & (($q_1$,1),(0,0),$R$) & (($q_1$,0),(1,0),$R$)    & (($q_1$,1),(1,0),$R$) &  -                      \tabularnewline
\hline
($q_0$,1)    & (($q_2$,0),(0,1),$R$)    & -                     & (($q_2$,0),(1,1),$R$)    & -                     &  -                      \tabularnewline
\hline
($q_1$,0)    & (($q_0$,0),(0,0),$D$)    & -                     & (($q_0$,0),(1,0),$D$)    & -                     &  -                      \tabularnewline
\hline
($q_1$,1)    & (($q_0$,1),(0,0),$D$)    & -                     & (($q_0$,1),(1,0),$D$)    & -                     &  -                      \tabularnewline
\hline
($q_2$,0)    & (($q_3$,0),(0,0),$U$)    & -                     & (($q_3$,0),(1,0),$U$)    & -                     &  (($q_5$,0),(\#,0),$L$) \tabularnewline
\hline
($q_2$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_3$,0)    & (($q_2$,0),(0,0),$R$)    & -                     & (($q_2$,0),(1,0),$R$)    & -                     &  (($q_4$,0),(\#,0),$D$) \tabularnewline
\hline
($q_3$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_4$,0)    & (($q_4$,0),(0,0),$L$)    & (($q_4$,0),(0,1),$L$) & (($q_4$,0),(1,0),$L$)    & (($q_4$,0),(1,1),$L$) &  (($q_0$,0),(\#,0),$R$) \tabularnewline
\hline
($q_4$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_5$,0)    & (($q_6$,0),(0,0),$U$)    & -                     & (($q_6$,0),(1,0),$U$)    & -                     &  -                      \tabularnewline
\hline
($q_5$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_6$,0)    & -                        & -                     &  -                       & -                     &  (($q_7$,0),(\#,0),$D$) \tabularnewline
\hline
($q_6$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_7$,0)    & (($q_8$,0),(0,0),$N$)    & -                     & (($q_{10}$,0),(1,0),$N$) & -                     &  -                      \tabularnewline
\hline
($q_7$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_8$,0)    & (($q_9$,0),(0,0),$L$)    & (($q_e$,1),(0,0),$N$) & (($q_9$,0),(1,0),$L$)    & -                     &  -                      \tabularnewline
\hline
($q_8$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_9$,0)    & (($q_8$,0),(0,0),$D$)    & -                     & (($q_8$,0),(1,0),$D$)    & -                     &  -                      \tabularnewline
\hline
($q_9$,1)    & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_{10}$,0) & (($q_{11}$,0),(0,0),$L$) & -                     & (($q_{11}$,0),(1,0),$L$) & (($q_e$,1),(1,0),$N$) &  -                      \tabularnewline
\hline
($q_{10}$,1) & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\hline
($q_{11}$,0) & (($q_{10}$,0),(0,0),$D$) & -                     & (($q_{10}$,0),(1,0),$D$) & -                     &  -                      \tabularnewline
\hline
($q_{11}$,1) & -                        & -                     &  -                       & -                     &  -                      \tabularnewline
\end{tabular}
\normalsize
\end{center}
\label{example_marker_automaton}
\end{example} 
The idea of $M$ is to mark the intersection of the two main diagonals. That is
why a marker will be moved along the first main diagonal step by step. After one
step $M$ checks if this position was the point of intersection. If $M$ has found
the intersection point it checks the second property.

The workflow of $M$ can be divided in four phases in which $M$ decides whether the
input picture is in its accepted language or not. The first three phases are
used to check where the point of the intersection of the two main diagonals
is and moreover to identify the size of the input picture. In the fourth phase $M$
verifies whether the symbols of the right upper corner and the one at the
intersection are the same. The four phases are illustrated in the following: 
\begin{center}
\begin{tabular}{cc}
\includegraphics[width = 3cm]{img/example_marker_automaton1.png} &
\includegraphics[width = 3cm]{img/example_marker_automaton2.png} \tabularnewline 
(a) The first phase. & (b) The second phase. \tabularnewline 
\includegraphics[width = 3cm]{img/example_marker_automaton3.png} &
\includegraphics[width = 3cm]{img/example_marker_automaton4.png} \tabularnewline 
(c) The third phase. & (d) The fourth phase.
\end{tabular}
\end{center}
Subsequently, the four phases are described in detail. In the first phase $M$
positions the marker along the first main diagonal. After every placing of the
marker $M$ changes to phase two starting at state $q_2$.

The second phase is needed to check if the marker is at the point of
intersection. Therefore, the automaton $M$ walks upwards along the second
main diagonal. If $M$ has scanned the border symbol in state $q_2$, the right
border has been reached and if the border symbol is scanned in state $q_3$,
the upper border was reached. If the automaton has detected the upper border
the marker is currently not at the cutting point thus the third phase starts
with state $q_4$.

The third phase is only needed to move $M$ to the left upper corner of the input
picture. After $M$ reaches position $(1, 1)$ it changes to phase one starting at
state $q_0$. These three phases will be repeated until $M$ has not detected
the right border in phase two with state $q_2$. If the right border was
identified $M$ checks the symbol of the upper left field of the current one.
If this symbol is the border symbol too, the input picture has the correct
size and the marker is placed at the intersection of the two main diagonals.
Afterwards, $M$ changes to phase four starting with state $q_7$.

At the start of the fourth phase, $M$ is at the right upper corner of the input
picture. Dependent on the current symbol $M$ changes its state. It changes
to state $q_8$ for the symbol $0$ and to $q_{10}$ for the symbol $1$. After $M$
switched the state it walks along the second main diagonal until $M$ finds the
marker on the diagonal. $M$ accepts the input picture if it scans the symbol $0$
in state $q_8$ or if it scans the symbol $1$ in state $q_{10}$ on the marker
position.
\begin{theorem}
$\familyOf{2DMA($k$)}$ and $\familyOf{2NMA($k$)}$ are closed under intersection
and union. Moreover, $\familyOf{2DMA($k$)}$ is closed under complement.
\end{theorem}
It was proved by A. Ito, K. Inoue and  Y. Wang in~\cite{ito1997nonclosure} that
any 2DMA($k$) can be converted to the 2DMA($k$) that always halts for any input.
From this lemma it follows that $\familyOf{2DMA($k$)}$ is closed under each
boolean operation. That $\familyOf{2NMA($k$)}$ is closed under intersection is
easy to show by using straightforward techniques, such as a serial concatenation
of two machines, as has been stated by A. Ito, K. Inoue and Y. Wang. 2NMA($k$) is
closed under union due to its existential states, where existential
states are those which have exactly one accepting computational
path~\cite{miyano1984alternating}.
\begin{theorem}
$\familyOf{2DMA(1)}$ and $\familyOf{2NMA(1)}$ are not closed under
concatenation operations, concatenation closure, cyclic closure and
projection.
\end{theorem}
\begin{proof}
In~\cite{ito1997nonclosure} it was proved that the language 
\begin{align*}
T' = \{p \in \{0,
1\}^{*,*} \mid \exists m (m \geq 2)[l_1(p) = m \text{ and } 
\exists i (2 \leq i \leq m)[p(1, *) = p(i, *)]]\}
\end{align*}
is in $\familyOf{2DMA(1)}$
and $T'^{RC} =  \{0, 1\}^{*,*} \vcat T'$ is not in $\familyOf{2NMA(1)}$,
which implies the nonclosure of the two classes under horizontal concatenation and row
cyclic closure. Then it was shown that $H' = T' \vcat S \vcat \{0, 1\}^{*,*}$,
where $S = \{p \in \{2\}^{*,*} \mid l_1(p) = 1\}$, is in $\familyOf{2DMA(1)}$
and $H'^+ = H' \cup T' \vcat (S \vcat \{0, 1\}^{*,*} \vcat T')^+ \vcat S \vcat
\{0, 1\}^{*,*}$ is not in $\familyOf{2NMA(1)}$, which implies the nonclosure
under horizontal concatenation closure. At least it was proved that the language 
\begin{align*}
R' = \{&p \in \{0, 1, (2, 0), (2, 1)\}^{*,*} \mid \exists m (m \geq 2)[l_1(p) = m \text{ and }\\
&\exists i, j (1 \leq i, j \leq m, i \neq j)[p(i, *), p(j, *) \in \{(2, 0), (2, 1)\}^{*,*} \text{ and }\\
&\forall r (1 \leq r \leq m, r \neq i, r \neq j)[p(k, *) \in \{0, 1\}^{*,*}] \text{ and }\\
&\tau(p(i, *)) = \tau(p(j, *))]]\}
\end{align*} 
with $\tau : \{0, 1, (2, 0), (2, 1)\} \mapsto \{0, 1\}, \tau(0) = 0, \tau(1) =
1, \tau((2,0)) = 0, \tau((2, 1)) = 1$ is in $\familyOf{2DMA(1)}$ and
$\bar{\tau}(R') \not\in \familyOf{2NMA(1)}$, where $\bar{\tau}$ is the
projection extended from the mapping $\tau$, which implies the nonclosure of the
two classes under projection.
\end{proof}
Let's speak about the language hierarchy. The following theorem was proved
by M. Blum and C. Hewitt in~\cite{blum1967automata}, which induces an
infinite chain of language relations.
\begin{theorem}
$\familyOf{2MA($k$)} \subset \familyOf{2MA($2k + 4$)}$, $k \geq 0$
\end{theorem}
The idea of the proof is that a $2k + 4$ marker automaton can decide if an
input picture has a certain property $P$, but no $k$-marker automaton can make
this decision.
Before we look at the following theorem note that 4FA $=$ 2MA($0$) with some
exceptions.
\begin{theorem}
$\familyOf{2MA($0$)} \subset \familyOf{2MA($1$)} \subset \familyOf{2MA($2$)}$
\end{theorem} 
In~\cite{blum1967automata} it was shown that a 2MA($1$) cannot decide
whether one simple-connected region is a translation of another, but it was also
said that it is trivial to prove whether a 2MA($2$) can do it. This is the
reason why a 2MA($2$) is more powerful than a 2MA($1$). The language $L_{1n =
cc}$ described in the Example~\ref{example_marker_automaton} is one reason why an
automaton with one marker is more powerful than an automaton without any marker.
A 4FA cannot accept the language $L_{1n = cc}$. Amongst others this was proved
in~\cite{blum1967automata}.
\begin{corollary} $\familyOf{2XMA($1$)} \not\subset \familyOf{2OTA}$ and
$\familyOf{2OTA} \not\subset \familyOf{2XMA($1$)}$, \\
for $X \in \{D, N\}$.
\end{corollary}
This corollary was proved by A. Ito, K. Inoue and Y. Wang
in~\cite{ito1997nonclosure}. The idea of this proof is that $\familyOf{2OTA}$ is
a subset from another language family, called the class of sets that are
accepted by n-space bounded three-way nondeterministic Turing machines, but
$\familyOf{2DMA(1)}$ is not. That implies $\familyOf{2DMA(1)} \not \subset
\familyOf{2OTA}$. For the other direction the following language is used: 
\begin{align*}
T(1) = \{p \in \{0, 1\}^{*,*} \mid &\exists n (n \geq 1)[l_2(p) = n \text{ and }\\
&\exists m (m \geq 2)[l_1(p) = m \text{ and }\\
&\exists i, j (1 \leq i, j \leq  m, i \neq j)[p(j, *) = p(i, *)]]]\}
\end{align*}
which is an element of $\familyOf{2OTA}$, but is no element of $\familyOf{2NMA(1)}$.

Further work about marker automata can be found in~\cite{ito1997nonclosure}
and~\cite{morita2004twodimensional}.